package singlelist;

import javax.xml.soap.Node;
import java.util.Stack;

public class SingleList {

    /**
     * 静态内部类
     * Node next很抽象，把节点抽象为了一个类
     * 因为next存的必须是节点的地址，所以类型也得是Node类型？
     */
    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }

        public Node() {}

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    static Node head;


    /**
     * 穷举创建一个四节点的单链表
     */
    public void createlist() {

        Node node1 = new Node(12);
        Node node2 = new Node(23);
        Node node3 = new Node(34);
        Node node4 = new Node(45);

        SingleList.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
    }

    public void displaySingleList () {
        Node cur = this.head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    public boolean contains (int i) {
        Node cur = this.head;
        while (cur != null) {
            if (i == cur.val) {
                return true;
            } else {
                cur = cur.next;
            }
        }
        return false;
    }

    public int size () {
        Node cur = this.head;
        int c = 0;
        while (cur != null) {
            c++;
            cur = cur.next;
        }
        return c;
    }

    public void addFirst (int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    public void addLast (int data) {
        Node newNode = new Node(data);
        if (this.head == null) {
            this.head = newNode;
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
        }
    }

    public void addIndex (int index, int data) throws IndexIllegalException {
        Node newNode = new Node(data);
        if (index == 0) {
            addFirst(data);
        } else if (index == size()) {
            addLast(data);
        }else if (index > size() || index < 0) {
            throw new IndexIllegalException("Index超出！");
        } else {
            Node cur = this.head;
            int c = 0;
            while(c != index - 1) {
                c++;
                cur = cur.next;
            }
            newNode.next = cur.next;
            cur.next = newNode;
        }
    }

    public void remove (int key) {
        Node before  = head;  //前驱节点
        if (before.val == key) {  //前驱节点（此时是head）的val == key
            if (head.next != null) {
                head = head.next;  //如果有下一个元素，就直接让head替换为下一个
                return;
            } else {
                head = null;  //如果没有下一个元素，就直接赋值为null
            }

        }
        while(before.next != null) {
            if (before.next.val == key) {
                before.next = before.next.next;  //让前一个节点的next不再指向被remove的节点，直接指向下一个节点
                return;
            }
            before = before.next;
        }
        System.out.println("Cannot find " + key + " in the list.");
    }

    public void removeAll (int key) {
        if (head == null) {
            return;
        }
        Node preNode = this.head;
        while(preNode.next != null) {  //1  1  2  1  1
            if (preNode.next.val == key) {
                preNode.next = preNode.next.next;
            } else {
                preNode = preNode.next;
            }
        }
        /**
         * 只有一个元素的时候不成立？
         * 成立！！只有一个元素的时候，head.next == null;
         * head = head.next 等价于 head = null;
         *
         * 一定要放在后面 避免后面还是出现head.val == key的情况
         */
        if (key == head.val) {
            head = head.next;
        }

        /**
         * 双指针法
         */
//        Node before = this.head;
//        if (before.next != null) {  //多个节点的情况
//            if (before.val == key) {
//                head = before.next;
//            }
//            Node cur = before.next;
//            while (cur.next != null) {
//                if (cur.val == key) {
//                    if (cur.next == null) {  //cur是最后一个节点
//                        cur = null;
//                    } else {
//                        before.next = cur.next;
//                    }
//                }
//                cur = cur.next;
//            }
//        } else if (before.val == key) {  //只有一个节点的情况
//            head = null;
//        }

//        Node before = this.head;
//        if (before.val == key) {  //第一个节点值就是key的情况
//            head = before.next;  //头节点后移
//        }
//        while(before.next != null) {  //中间节点值是key的情况
//            if (before.next.val == key) {  //before的下一个节点的val是key 就跳过
//                before.next = before.next.next;
//            } else {
//                before = before.next;
//            }
//        }
//        if (before.val == key) {  //尾节点是key的情况
//            before = null;
//        }
//        return;
    }

    public void clear () {
        head = null;
    }
}

class Ts {
    public static void main(String[] args) {
        SingleList singleList = new SingleList();
        singleList.addLast(1);
//        singleList.addLast(1);
//        singleList.addLast(2);
//        singleList.addLast(1);
//        singleList.addLast(1);
        System.out.println();
        singleList.displaySingleList();
        singleList.removeAll(1);
        System.out.println();
        singleList.displaySingleList();

    }

    public static void main3(String[] args) {
        SingleList singleList = new SingleList();
        singleList.addLast(1);
        singleList.addLast(2);
        singleList.addLast(3);
        singleList.addLast(4);
        singleList.addLast(5);
        singleList.displaySingleList();
        System.out.println("===");
        System.out.println();
        singleList.addIndex(0,99);
        singleList.displaySingleList();
        System.out.println("===");
        System.out.println();
        singleList.addIndex(6,100);
        singleList.displaySingleList();
    }

    public static void main2(String[] args) {
        SingleList singleList = new SingleList();
        singleList.addFirst(7);
        singleList.addFirst(6);
        singleList.addFirst(5);
        singleList.addFirst(4);
        singleList.addFirst(3);
        singleList.addFirst(2);
        singleList.addFirst(1);
        singleList.displaySingleList();
        System.out.println("========");

        singleList.remove(1);
        singleList.displaySingleList();
        System.out.println();
        System.out.println("========");
        singleList.remove(7);
        singleList.displaySingleList();
        System.out.println();
        System.out.println("========");
        singleList.remove(4);
        singleList.displaySingleList();
        System.out.println();
    }

    /**
     * 单链表add
     * @param args
     */
    public static void main1(String[] args) {
        SingleList singleList = new SingleList();
        singleList.createlist();
        singleList.addFirst(45);
        singleList.addFirst(34);
        singleList.addFirst(23);
        singleList.addFirst(12);
        singleList.addLast(99);

        singleList.addIndex(3,22);

        singleList.displaySingleList();
        System.out.println();
        System.out.println(singleList.contains(13));
        System.out.println(singleList.size());

    }
}

